package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

/**
 * @author By ZengPeng
 */
public class 力扣_11_盛最多水的容器 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_11_盛最多水的容器().maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println(new 力扣_11_盛最多水的容器().maxArea(new int[]{1,1}));
    }

    /**
    题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     返回容器可以储存的最大水量。
     说明：你不能倾斜容器。

     示例 1：
     输入：[1,8,6,2,5,4,8,3,7]
     输出：49
     解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

     示例 2：
     输入：height = [1,1]
     输出：1

    分析：【P 💙💚💜】
       1.变量当前面积最大值，面积 = (right -left +1 ) * min(right,left) -- 【超时了】
       2.如果左边小：移动左边 left ? left+1
                --执行用时：4 ms, 在所有 Java 提交中击败了67.10%的用户
            优化：直接找到下一个计算的点，剪切不必要的计算
                --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public int maxArea(int[] height) {
        // 2.如果左边小：移动左边 left ? left+1
        int max=0,left=0,right=height.length-1;
        while(left<right){
            int deep=Math.min(height[left],height[right]);
            max=Math.max(max,(right-left)*deep);
            while(height[left] <= deep && left < right) left++;
            while(height[right] <= deep && left < right) right--;
        }
        return max;

       /*1.变量当前面积最大值，面积 = (right -left +1 ) * min(right,left) -- 【超时了】
         int max=0;
         for (int i = 0; i < height.length-1; i++) {
            int pro=height[height.length-1];
            for (int j = height.length-1; j > i; j--) {
                if(height[j]<pro)continue;
               max = Math.max(max,(j-i)*Math.min(height[i],height[j]));
               pro=height[j];
            }
        }
        return max;*/
    }
}
